#include "param.h"
#include "types.h"
#include "memlayout.h"
#include "elf.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"

// 名称以kvm开头的函数操作内核页表；以uvm开头的函数操作用户页表；其他函数用于二者

/*
 * the kernel's page table.
 全局内核页表
 */
pagetable_t kernel_pagetable;

extern char etext[];  // kernel.ld sets this to end of kernel code.

extern char trampoline[]; // trampoline.S

/*
 * create a direct-map page table for the kernel.
 初始化全局内核页表
 */
void
kvminit()
{
  kernel_pagetable = kvminit_pgt();
  // 全局页表自身需要CLINT
  kvmmap(kernel_pagetable, CLINT, CLINT, 0x10000, PTE_R | PTE_W);
}

// 初始化一个新的内核页表
pagetable_t kvminit_pgt() {
  // 为新内核页表开辟空间
  pagetable_t pgt = (pagetable_t) kalloc();
  memset(pgt, 0, PGSIZE);

  // 为这个新页表添加固定映射
  // uart registers
  kvmmap(pgt, UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface 硬盘界面
  kvmmap(pgt, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // CLINT
  // xv6只有在内核初始化时用到CLINT，因此为用户进程生成内核页表时，可以不必映射这段地址。
  // CLINT的地址在PLIC之前, 属于用户进程空间可用的虚拟地址, 如果留着会产生冲突
  // kvmmap(pgt, CLINT, CLINT, 0x10000, PTE_R | PTE_W);

  // PLIC
  kvmmap(pgt, PLIC, PLIC, 0x400000, PTE_R | PTE_W);

  // map kernel text executable and read-only.
  kvmmap(pgt, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);

  // map kernel data and the physical RAM we'll make use of.
  kvmmap(pgt, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);

  // map the trampoline for trap entry/exit to
  // the highest virtual address in the kernel.
  kvmmap(pgt, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);

  return pgt;
}

// 后序遍历递归释放内核页表
void kvmfree_pgt(pagetable_t pagetable) {
  // there are 2^9 = 512 PTEs in a page table.
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    uint64 child = PTE2PA(pte);
    // 如果页表项有效且该节点 还有子节点 则先递归释放其子节点页表项
    if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
      kvmfree_pgt((pagetable_t)child);
      pagetable[i] = 0;  
    } 
  }
  // 释放当前页表
  kfree((void*)pagetable);
}

// Switch h/w page table register to the kernel's page table,
// and enable paging.
// 安装内核页表
void
kvminithart()
{
  // 将内核页表根页表页的物理地址写入寄存器satp
  w_satp(MAKE_SATP(kernel_pagetable));
  // RISCV的一个指令 用于刷新当前CPU的TLB
  // xv6更改页表时，它必须告诉CPU使相应的缓存TLB条目无效
  sfence_vma();
}

// Return the address of the PTE in page table pagetable
// that corresponds to virtual address va.  If alloc!=0,
// create any required page-table pages.
//
// The risc-v Sv39 scheme has three levels of page-table
// pages. A page-table page contains 512 64-bit PTEs.
// A 64-bit virtual address is split into five fields:
//   39..63 -- must be zero.
//   30..38 -- 9 bits of level-2 index.
//   21..29 -- 9 bits of level-1 index.
//   12..20 -- 9 bits of level-0 index.
//    0..11 -- 12 bits of byte offset within the page.
// 根据虚拟地址获得页表相应的页表项
// 虚拟地址39位中的前27位索引页表，以找到该虚拟地址对应的一个PTE
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  if(va >= MAXVA)
    panic("walk");
  // 一次从3级页表中获取9个比特位。它使用上一级的9位虚拟地址来查找下一级页表或最终页面的PTE
  for(int level = 2; level > 0; level--) {
    pte_t *pte = &pagetable[PX(level, va)];
    
    if(*pte & PTE_V) {
      pagetable = (pagetable_t)PTE2PA(*pte);
    } 
    // 如果PTE无效，则所需的页面还没有分配
    else {
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      // 如果设置了alloc参数，walk就会分配一个新的页表页面，并将其物理地址放在PTE中
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  // 返回树中最低一级的PTE地址
  return &pagetable[PX(0, va)];
}

// Look up a virtual address, return the physical address,
// or 0 if not mapped.
// Can only be used to look up user pages.
// 地址变换机构
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0)
    return 0;
  if((*pte & PTE_V) == 0)
    return 0;
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}

// add a mapping to a kernel page table.
// only used when booting.
// does not flush TLB or enable paging.
// 为给定的内核页表添加映射
// 原始方案中默认为全局内核页表添加 现在需要对指定的内核页表添加
void
kvmmap(pagetable_t pgt,uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(pgt, va, sz, pa, perm) != 0)
    panic("kvmmap");
}

// translate a kernel virtual address to
// a physical address. only needed for
// addresses on the stack.
// assumes va is page aligned.
// 把一个内核页表的虚拟地址翻译为物理地址
// 原始方案中默认从全局内核页表去找地址
uint64
kvmpa(pagetable_t pgt, uint64 va)
{
  uint64 off = va % PGSIZE;
  pte_t *pte;
  uint64 pa;
  
  pte = walk(pgt, va, 0);
  if(pte == 0)
    panic("kvmpa");
  if((*pte & PTE_V) == 0)
    panic("kvmpa");
  pa = PTE2PA(*pte);
  return pa+off;
}

// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa. va and size might not
// be page-aligned. Returns 0 on success, -1 if walk() couldn't
// allocate a needed page-table page.
// 将范围虚拟地址到同等范围物理地址的映射装载到一个页表中。它以页面大小为间隔，为范围内的每个虚拟地址单独执行此操作。
// perm为标志位
// 一个页表项对应一个页面 将每一个页面的页号保存在pte里
int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
  uint64 a, last;
  pte_t *pte;

  a = PGROUNDDOWN(va);
  last = PGROUNDDOWN(va + size - 1);
  for(;;){
    // 调用walk来查找该地址的PTE地址。然后，
    if((pte = walk(pagetable, a, 1)) == 0)
      return -1;
    if(*pte & PTE_V)
      panic("remap");
    // 它初始化PTE以保存相关的物理页号、所需权限 以及用于标记PTE有效的PTE_V
    *pte = PA2PTE(pa) | perm | PTE_V;
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

// Remove npages of mappings starting from va. va must be
// page-aligned. The mappings must exist.
// Optionally free the physical memory.
// If do_free != 0, physical memory will be freed
// 解除映射 并决定是否释放对应地址空间
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;

  if((va % PGSIZE) != 0)
    panic("uvmunmap: not aligned");

  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
      panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}

// create an empty user page table.
// returns 0 if out of memory.
pagetable_t
uvmcreate()
{
  pagetable_t pagetable;
  pagetable = (pagetable_t) kalloc();
  if(pagetable == 0)
    return 0;
  memset(pagetable, 0, PGSIZE);
  return pagetable;
}

// Load the user initcode into address 0 of pagetable,
// for the very first process.
// sz must be less than a page.
void
uvminit(pagetable_t pagetable, uchar *src, uint sz)
{
  char *mem;

  if(sz >= PGSIZE)
    panic("inituvm: more than a page");
  mem = kalloc();
  memset(mem, 0, PGSIZE);
  mappages(pagetable, 0, PGSIZE, (uint64)mem, PTE_W|PTE_R|PTE_X|PTE_U);
  memmove(mem, src, sz);
}

// Allocate PTEs and physical memory to grow process from oldsz to
// newsz, which need not be page aligned.  Returns new size or 0 on error.
uint64
uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  char *mem;
  uint64 a;

  if(newsz < oldsz)
    return oldsz;

  oldsz = PGROUNDUP(oldsz);
  for(a = oldsz; a < newsz; a += PGSIZE){
    mem = kalloc();
    if(mem == 0){
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE);
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
      kfree(mem);
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
  }
  return newsz;
}

// Deallocate user pages to bring the process size from oldsz to
// newsz.  oldsz and newsz need not be page-aligned, nor does newsz
// need to be less than oldsz.  oldsz can be larger than the actual
// process size.  Returns the new process size.
uint64
uvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  if(newsz >= oldsz)
    return oldsz;

  if(PGROUNDUP(newsz) < PGROUNDUP(oldsz)){
    int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
    uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1);
  }

  return newsz;
}

// 递归释放页表页 必须保证所有叶子节点已经被释放了
// Recursively free page-table pages.
// All leaf mappings must already have been removed.
void
freewalk(pagetable_t pagetable)
{
  // there are 2^9 = 512 PTEs in a page table.
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    // 如果页表项有效且该节点不是叶子节点
    // 叶子节点W位，R位，X位起码有一位会被设置为1
    if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
      // this PTE points to a lower-level page table.
      uint64 child = PTE2PA(pte);
      freewalk((pagetable_t)child);
      pagetable[i] = 0;  
    } else if(pte & PTE_V){
      panic("freewalk: leaf");
    }
  }
  kfree((void*)pagetable);
}

// Free user memory pages,
// then free page-table pages.
// 释放用户内存页 然后释放页表页
void
uvmfree(pagetable_t pagetable, uint64 sz)
{
  if(sz > 0)
    uvmunmap(pagetable, 0, PGROUNDUP(sz)/PGSIZE, 1);
  freewalk(pagetable);
}

// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
// 用户页表的复制
// 默认从0地址开始复制sz个页面
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  char *mem;

  // 从0地址开始 到整个pgt大小
  for(i = 0; i < sz; i += PGSIZE){
    // 如果页表项不存在
    if((pte = walk(old, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    // 如果页表不存在
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");
    // 找到页表项的物理地址 
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    // 分配物理页内存，如果分配内存失败
    if((mem = kalloc()) == 0)
      goto err;
    // 拷贝实际的物理页内存
    memmove(mem, (char*)pa, PGSIZE);
    // 将物理地址映射到新的页表的第i个页表项上
    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
      kfree(mem);
      goto err;
    }
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}



// 用户页表拷贝到内核页表
// 从old页表给的的va开始往后sz个页面复制到new
// 仅仅复制页表项 不拷贝实际物理内存
// 参考uvmcopy实现
int
kvmcopy(pagetable_t old, pagetable_t new, uint64 va, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  // 从va地址开始 到给定的范围大小
  for(i = PGROUNDUP(va); i < va + sz; i += PGSIZE){
    // 如果页表项不存在
    if((pte = walk(old, i, 0)) == 0)
      panic("kvmcopy: pte should exist");
    // 如果页表不存在
    if((*pte & PTE_V) == 0)
      panic("kvmcopy: page not present");
    // 找到页表项的物理地址 
    pa = PTE2PA(*pte);
    // 去除PTE_U标志以保证内核能够访问该用户页
    flags = PTE_FLAGS(*pte) & ~PTE_U;
    // 将物理地址映射到新的页表的第i个页表项上
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}


// 参考uvmdealloc实现
// 为内核页表newsz到oldsz的地址解除映射
uint64
kvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  if(newsz >= oldsz)
    return oldsz;

  if(PGROUNDUP(newsz) < PGROUNDUP(oldsz)){
    int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
    // do_free为0 不释放地址空间
    uvmunmap(pagetable, PGROUNDUP(newsz), npages, 0);
  }

  return newsz;
}


// mark a PTE invalid for user access.
// used by exec for the user stack guard page.
void
uvmclear(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  
  pte = walk(pagetable, va, 0);
  if(pte == 0)
    panic("uvmclear");
  *pte &= ~PTE_U;
}

// Copy from kernel to user.
// Copy len bytes from src to virtual address dstva in a given page table.
// Return 0 on success, -1 on error.
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    memmove((void *)(pa0 + (dstva - va0)), src, n);

    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

// Copy from user to kernel.
// Copy len bytes to dst from virtual address srcva in a given page table.
// Return 0 on success, -1 on error.
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  return copyin_new(pagetable, dst, srcva, len);
}

// Copy a null-terminated string from user to kernel.
// Copy bytes to dst from virtual address srcva in a given page table,
// until a '\0', or max.
// Return 0 on success, -1 on error.
int
copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
{
  return copyinstr_new(pagetable, dst, srcva, max);
}

// check if use global kpgtbl or not 
int 
test_pagetable()
{
  uint64 satp = r_satp();
  uint64 gsatp = MAKE_SATP(kernel_pagetable);
  return satp != gsatp;
}


// 递归打印页表页及其子节点 
void
vmprint(pagetable_t pagetable, int depth)
{
  // there are 2^9 = 512 PTEs in a page table.
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];

    // 如果页表项有效则对其进行打印 
    if(pte & PTE_V) {
      printf("||");
      int d = 1;
      // 根据页表项层数打印缩进
      while(d++ <= depth){
        printf(" ||");
      }
      
      uint64 child = PTE2PA(pte);

      // 打印页表项内容
      printf("%d: pte %p pa %p\n", i, pte, child);

      // 如果当前页表项还有子节点 则递归打印
      // 叶子节点的 R W X至少有一项是1
      if((pte & (PTE_R|PTE_W|PTE_X)) == 0){
        // this PTE points to a lower-level page table.
        vmprint((pagetable_t)child, depth+1);
      } 
    }

  }
}